package leetcode.code1658;

import java.util.HashMap;
import java.util.Map;

import leetcode.helper.MaxDebug;

public class Solution1 extends S1658 {

	@Override
	public int minOperations(int[] nums, int x) {
		int Len = nums.length;
		int[] sum = new int[Len + 1];
		Map<Integer, Integer> hash = new HashMap<>();
		hash.put(0, 0);// 一个数没有，累加和是0
		int tmp = 0;
		for (int i = 1; i <= Len; i++) {// 1~Len个数的累加和
			hash.put(tmp = sum[i - 1] + nums[i - 1], i);
			sum[i] = tmp;
		}
		int target = sum[Len] - x;
		if (target < 0)
			return -1;
		int ans = Integer.MAX_VALUE;
		for (int i = Len; i > 0 && sum[i] >= target; i--) {
			if (hash.containsKey(tmp = sum[i] - target)) {// [hash.get(tmp)+1,i]累加和==target
				ans = Math.min(ans, Len - i + hash.get(tmp));// Len - (i - hash.get(tmp)) 两边去掉的数字个数
			}
		}
		return ans == Integer.MAX_VALUE ? -1 : ans;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug4();
		MaxDebug.debug14(so);

	}

}
